//仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。 
//
//
// 
//
// 示例 1： 
//
// 
//输入：stock = [2,5,7,4], cnt = 1
//输出：[2]
// 
//
// 示例 2： 
//
// 
//输入：stock = [0,2,3,6], cnt = 2
//输出：[0,2] 或 [2,0] 
//
// 
//
// 提示： 
//
// 
// 0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000 
// 
//
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 600 👎 0


package LeetCode.editor.cn;


import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-05-14 10:29:07
 * @description LCR 159.库存管理 III
 
 */
 
public class ZuiXiaoDeKgeShuLcof {
    public static void main(String[] args) {
    //测试代码
    ZuiXiaoDeKgeShuLcof fun = new ZuiXiaoDeKgeShuLcof();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] inventoryManagement1(int[] stock, int cnt) {
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        for (int i = 0; i < stock.length; i++) {
            pq.add(stock[i]);
        }
        int[] res=new int[cnt];
        for (int i = 0; i < cnt; i++) {
            res[i]=pq.poll();
        }
        return res;
    }
    public int[] inventoryManagement(int[] stock, int cnt) {
        int n = stock.length;
        int[] res = new int[cnt];
        if (cnt == 0) return res;
        // 使用快速选择算法
        quickSelect(stock, 0, n - 1, cnt);
        // 将前 cnt 个元素放入结果数组
        System.arraycopy(stock, 0, res, 0, cnt);
        return res;
    }
    private void quickSelect(int[] arr, int left, int right, int k) {
        if (left >= right) return;
        int pivotIndex = partition(arr, left, right);
        if (pivotIndex == k - 1) return; // 找到第 k 小的元素
        else if (pivotIndex < k - 1) quickSelect(arr, pivotIndex + 1, right, k);
        else quickSelect(arr, left, pivotIndex - 1, k);
    }
    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, right);
        return i;
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
